Методи розв'язання алгебраїчних рівнянь
1. Однокрокові ітераційні моделі
Для вирішення рівнянь часто вдаються до ітераційним методам, які іноді називають методами послідовних наближень.
Суть цього класу методів можна розкрити на прикладі.
Нехай нам потрібно вирішити рівняння:
(1)
для вирішення цього рівняння будується відповідна Ітераційна формула:
(2)
Задаючи початкове наближення кореня рівняння (1) у вигляді:
(3)
знаходимо подальші наближення за формулою (2):
(4),
(5),
(6)
Ми бачимо, що кожне обчислена значення стає вихідним для обчислення наступних наближень
.
Такі ітераційні формули називаються однокроковими.
Існують і двухшаговим, трехшаговие і т.д. ітераційні формули, які визначаються відповідно формулами:
- Двухшаговим формула (7)
- Трехшаговие формула (8)
і т.д.
Після побудови ітераційної формули (2) виникають питання:
а) скільки потрібно вважати послідовних наближень , Тобто коли зупинитися?
б) сходиться чи послідовність наближень до кореня
?
Відповіді на ці питання потрібно давати завжди, коли маємо справу з методом послідовних наближень Пікара. На запитання відповідають наступним чином:
а) задається точність обчислень і ітераційний процес зупиняють, як тільки досягається відповідна абсолютна похибка, тобто як тільки виконується умова:
(9)
б) потрібно відповідним чином будувати формули (2), використовуючи відповідні теореми про достатню умови збіжності. Зокрема теорему Банаха про стислих відображеннях.
Визначення: Нехай M - метричний простір з метрикою . Оператор A, що відображає цей простір в себе називається стискає, якщо існує таке число
, Що для будь-якої пари елементів
має місце нерівність:
(10)
Т.ч. стискає оператор стискає відстань між елементами і
, Тобто відстань між образами елементів
менше або дорівнює відстані між їх прообразами
і
. Для таких відображень використовується теорема Банаха. Теорема Банаха: Нехай A - стискає оператор в повному метричному просторі M, тоді рівняння
(11)
має в цьому просторі один і тільки одне рішення, тобто існує рівно один елемент , Для якого виконується рівняння
. Цей елемент може бути отриманий як межа послідовності елементів
(12)
де , Причому елемент
може бути вибраний довільно. Ця теорема застосовна і для випадку, коли оператор
- Є функцією, тобто для формули (2), а також для побудови сходяться ітераційних формул Рітца-Якобі в разі лінійних систем алгебраїчних рівнянь з погано обумовленою матрицею (визначник близький до нуля) коефіцієнтів, для диференціальних та інтегральних операторів і т.д. Для ітераційної формули (2), застосовуючи формулу Лагранжа про кінцеві прирости, отримуємо, що для
має місце співвідношення:
(13)
що зі свого боку можна переписати у вигляді
(14)
якщо Чебишевская норма функцій , Тобто якщо
(15)
У такому випадку відображення з (2) є стискає і, відповідно, для неї має місце теорема Банаха.Т. е. Ітераційна формула (2) дозволяє знайти корінь
рівняння (1) за формулою
(16)
Незважаючи на уявну простоту, ітераційні формули виду (2) таять в собі багато цікавих ефектів. Для розкриття деяких з них розглянемо найпростішу нелінійну итерационную формулу, що виникає в задачі про еволюцію грошових вкладів.
2. Виникнення хаосу в детермінованих системах
Нехай - Кількість грошових вкладів за
років. Коефіцієнт відносного приросту вкладів позначимо через
. Тоді маємо:
(17)
тобто , Де
(18)
Для дослідження динаміки процесу перепишемо (18) у вигляді:
(19)
Ясно, що якщо початкове значення грошового вкладу було , Тоді
(20)
з (20) випливає, що зі зростанням n, кількість грошових вкладів необмежено збільшується, т.к .
Формула (20) дозволяє вирішити задачу про допустимі відсотках зростання R. Наприклад, з'ясуємо, яким повинен бути R для подвоєння вкладів відбувалося за 50 років. Маємо:
(21)
Тоді
(22)
тобто
(23)
Тепер припустимо, що рада директорів банку вирішила збільшити коефіцієнт приросту R - для залучення клієнтів, але щоб захистити себе від банкрутства вирішив не допускати подальшого збільшення вкладів якщо величина досягає значення , Після чого коефіцієнт повинен стає негативним, тобто зменшувати вклади поки не опустяться нижче
, Для цього вирішили, що
. Тоді з (17) отримуємо:
(24)
де . Тоді маємо:
(25)
Досліджуємо точки рівноваги системи (25), тобто ті значення вкладів , Які з ростом n, не змінюються (або інакше
).
Очевидно, що такими значеннями служать:
а) і б)
.
Для того, щоб точка рівноваги реалізувалася на практиці потрібна її стійкість, інакше мале збурення може її швидко вивести зі стану, так що ми й ахнути не встигнемо. Тому, досліджуємо ці стани на стійкість.
а) Розглянемо спочатку стан рівноваги , Тобто стан, коли на вашому рахунку грошей нет.д.обавім мале "обурення" точці рівноваги
і досліджуємо її динаміку з часом: тобто
, Тоді з (25) отримуємо:
(27)
т.к , Ясно, що
тому нею можна знехтувати в (27). Внаслідок маємо:
(29)
звідси, легко отримати, що
(29)
тобто обурення наростають з часом, що зі свого боку означає нестійкість точки рівноваги . За змістом же, завдання це означає зростання вкладу з часом, якщо хоч якась мала сума грошей
села на рахунок.
б) Досліджуємо тепер стійкість другої точки рівноваги: . Тут також дамо малий приріст
до точки рівноваги, тобто розглянемо значення
і досліджуємо динаміку цього стану з плином часу n. З (25) отримуємо:
(30)
Провівши перетворення, маємо:
Враховуючи, що і тому, нехтуючи нею отримуємо:
(31)
для стійкості точки рівноваги , Має виконуватися умова:
(32)
тобто
(Рис.1)
(33)
ця умова зі свого боку означає, що
(34)
таким чином, якщо ми виберемо як відносного коефіцієнта зростання:
(Рис.2)
(35)
той стан буде стійким, інакше ми вступаємо в зону нестійкостей, яка сповнена несподіванками. Зокрема, при
, (Рис.3) виникають періодичні коливання
(Рис.1). При
картина ускладнюється і з'являється двоякоперіодіческіе коливання (рис.2) При подальшому зростанні відносного коефіцієнта приросту, отримуємо учетверение періоду і т.д., в разі
спостерігаються хаотичні коливання (рис.3).
Таким чином, нелінійні ітераційні формули типу (2) приховують в собі безліч таємниць і для їх розкриття потрібні додаткові дослідження в кожному конкретному випадку. Тим більше, що не завжди вдається оцінити збіжність ітераційного процесу глобально.
Цей приклад хоч і є окремим випадком формули (2), але наводить на роздуми корисні. Вищевикладена Ітераційна формула (25) вперше була побудована для вивчення динаміки популяцій особин певного виду в залежності від винищування ареалу їжі Ферхюльста і носить його ім'я.
Ми бачимо, що одна і та ж математична модель може містити в собі різні аспекти програм, що цілком характерно для духу прикладної математики.
3. Методи розв'язання алгебраїчних рівнянь
Більшість задач фізики, економіки, соціології, біології та інших областей знання приводять до вирішення алгебраїчних рівнянь або систем рівнянь.
Незважаючи на наявність безлічі наближених методів, в даний час, мабуть, немає загального підходу для вирішення будь-якого нелінійного рівняння і тим більше нелінійної системи рівнянь. Тому, в кожному окремому випадку доводиться досліджувати рівняння і будувати відповідні алгоритми, комбінуючи ідеї різних чисельних методів. Так, що рішення нелінійного рівняння, в даний час, швидше мистецтво, ніж наука. Хоча, відомі програмні продукти сучасних фірм дозволяють, у багатьох випадках, спростити пошук коріння.
Перейдемо на виклад основних відомих і найбільш популярних методів. Перш відзначимо, що при знаходженні наближених значень коренів доводиться вирішувати два завдання:
а) відділення коренів, тобто відшукання досить малих областей в кожній з яких знаходиться корінь;
б) обчислення коренів із заданою точністю.
3.1 Метод поділу відрізка навпіл (метод дихотомії)
Перед початком вирішення рівняння
(36)
ми повинні виділити інтервал пошуку рішення , Тобто відповісти на питання а) попереднього параграфа. Для цього використовується теорема Вейєрштрасса.
Теорема Вейєрштрасса: Якщо на кінцях деякого відрізка безперервна функція приймає значення різних знаків, то на цьому відрізку рівняння (36) має хоча б один корінь.
Ця теорема висловлює геометрично очевидний факт (рис.4), що складається в тому, що якщо в точках і
графік неперервної функції знаходиться в
різних напівплощини від осі , То знайдеться точка
, Така що графік цієї функції перетинається з віссю
в точці
, Тобто
.
а b Зауваження: якщо при цьому
має першу
похідну - Не міняє знаку, то корінь єдиний.
Таким чином, ми можемо сказати, що вже вміємо
Рис. знаходити відрізок , Де знаходиться корінь
рівняння (36), але цей відрізок можна зменшувати, грунтуючись на теоремі Вейерштрасса.
Для цього в якості першого наближення до кореня беремо середину відрізка , Тобто
(38)
Цією точкою відрізок ділиться на два рівних відрізки:
і
. Використовуючи теорему Вейєрштрасса, встановлюємо в якому з цих відрізків лежить корінь, тобто на кінцях якого з цих двох відрізків функція
приймає різні знаки. З цим відрізком діємо також, тобто вибираємо в якості другого наближення до кореня середину цього відрізка
і продовжуємо цей ітераційний процес, поки відрізок пошуку рішення
не стане менше необхідної точності
.
Оцінка похибки обчислень за методом поділу відрізка навпіл проводиться за очевидною формулою:
(39)
Ясно, що , А відносна похибка
.
Викладений метод легко програмується і дає збіжність з точністю (39), хоча при практичних обчисленнях частіше користуються комбінаціями різних чисельних методів, домагаючись більш швидкої збіжності процесу.
3.2 Метод помилкового положення (метод хорд).
В основі методу лежить лінійна інтерполяція за двома значеннями функції, які мають протилежні знаки. Цей метод часто дає більш швидку збіжність, ніж метод поділу відрізка навпіл.
Для ілюстрації алгоритму методу помилкового положення (методу хорд), розглянемо рис.5.
рис.5.
Спочатку знаходимо відрізок де
y завідомо відомо, що існує
корінь , Тобто
, Для цього по теоремі Вейерштрасса повинно бути
.
В якості першого наближення до кореня беремо , Друге наближення
. Для знаходження наступного наближення з'єднуємо ці дві точки відрізком прямої. Точку перетину цього відрізка беремо в якості третьої наближення
, Далі значення функції
порівнюється з
і
, Де будуть різні знаки, надалі використовується саме той відрізок замість
, І т.д. Відповідна Ітераційна формула має вигляд:
(40)
де і
.
Ясно, що ця Ітераційна формула вимагає, щоб , А також
і
.
Точність обчислення кореня методом хорд оцінюється нерівністю
(41)
гранична відносна похибка:
(42)
де .
3.3 Метод Ньютона (метод дотичних)
Хоча метод помилкового положення дає більш швидку збіжність, ніж метод поділу відрізка навпіл, перевірка умов застосовності методу хорд досить громіздка, тому розглянемо метод Ньютона, який іноді називають методом дотичних.
На відміну від попередніх методів тут не потрібно попередньо шукати відрізок , Де
. Для рішення рівняння
(43)
в методі Ньютона задаємося необхідною точністю (Абсолютна похибка). Далі довільно вибираємо початкове наближення
. Вважаємо, що
(44)
для знаходження наступного наближення , Де
(45)
скористаємося формулою Тейлора для :
(46)
Відкидаючи члени розкладання, що містять похідні вище першого порядку, отримуємо рівняння для визначення наближеного значення кореня :
(47)
тобто
(48)
Знаючи , Нове, покращене значення
знаходимо аналогічно
(49)
і взагалі
(50)
Обчислення треба продовжувати до тих пір, поки не досягнемо необхідної абсолютної похибки :
(51)
Гранична відносна похибка дорівнює:
(52)
Швидкість збіжності ітераційної формули Ньютона (50) оцінюється нерівністю:
(53)
Ясно, що швидкість збіжності вище, ніж в методі хорд. Однак, тут так само потрібно мати на увазі, що , А також
і
, А ці умови важко перевірити, що і є відштовхуючим фактором для дослідників. Крім того, для застосування методу Ньютона, потрібно досить точне знання початкового наближення
.
Тут, так само як і в методі хорд, легко представити цей процес геометрично. Взявши початкове наближення , В цій точці проводиться дотична до графіка функції
. Перетин дотичної з віссю абсцис
приймається за перше наближення. Далі дотична проводиться в точці
, Перетин дотичній з віссю
береться в якості другого наближення і т.д.
Література
1. Вища математика - Сапунов І.С. - М. 2000